double* devidedDifference(double* x, double* y,  int n) {
    int k = 0;
    double* f=new double [n*(n-1)/2];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (i == 0) {
                f[k] = (y[j + 1] - y[j]) / (x[j + 1] - x[j]);
            } else {
                f[k] = (f[k - (n - i - 1)] - f[k - (n - i - 1) - 1]) / (x[j + i + 1] - x[j]);
            }
            k++;
        }
    }
    return f;
}

// 计算 Newton 插值多项式的值
double Newton(double* x, double* y, int n, double a) {
    double* b = new double[n];
    double* f=new double [n*(n-1)/2];
    f=devidedDifference(x,y,n);
    b[0] = 1;
    for (int i = 0; i < n - 1; i++) {
        b[i + 1] = b[i] * (a - x[i]);
    }
    double result = y[0];
    int k = 0;
    for (int i = 1; i < n; i++) {
        result += b[i] * f[k];
        k += (n - i);
    }
    delete[] f;
    delete[] b; // 释放动态分配的内存
    return result;
}
